/*
 * @lc app=leetcode.cn id=90 lang=cpp
 *
 * [90] 子集 II
 */

// @lc code=startclass Solution
class Solution
{
private:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int> &nums, int index, vector<bool> &used)
    {
        //可能有重复 需要去重 借助used判断
        res.push_back(path); //空集
        if (index >= nums.size())
        {
            return;
        }
        for (int i = index; i < nums.size(); i++)
        {
            //去重
            if (i > index && nums[i] == nums[i - 1] )
            {
                continue;
            }
            path.push_back(nums[i]);
            backtracking(nums, i + 1, used);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> subsetsWithDup(vector<int> &nums)
    {
        //可能出现重复元素 需要去重
        //注意树层和树枝的去重逻辑
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false); //去重
        backtracking(nums, 0, used);
        return res;
    }
};
// @lc code=end
